﻿namespace AlgorithmInterview.Chapter02._08;

/// <summary>
/// 实现LRU缓存方案
/// </summary>
public class LRU
{
    private int cacheSize;
    private LinkedList<int> queue = new LinkedList<int>();
    private HashSet<int> hashSet = new HashSet<int>();

    public LRU(int cacheSize)
    {
        this.cacheSize = cacheSize;
    }

    /// <summary>
    /// 判断缓存队列是否已满
    /// </summary>
    /// <returns></returns>
    private bool IsQueueFull()
    {
        return queue.Count() == cacheSize;
    }

    /// <summary>
    /// 把页号为pageNum的也缓存到队列中，同时也添加到Hash表中
    /// </summary>
    /// <param name="pageNum"></param>
    private void Enqueue(int pageNum)
    {
        // 如果队列满了，需要删除队尾的缓存项
        if (IsQueueFull())
        {
            hashSet.Remove(queue.Last());
            queue.RemoveLast();
            ;
        }

        queue.AddFirst(pageNum);

        // 把心缓存的结点同时添加到Hash表中
        hashSet.Add(pageNum);
    }


    public void AccessPage(int pageNum)
    {
        // page 不在缓存队列中，把它缓存到队首
        if (!hashSet.Contains(pageNum))
        {
            Enqueue(pageNum);
        }
        // page 已经在缓存队列中了，移动到队首
        else if (pageNum != queue.First())
        {
            queue.Remove(pageNum);
            queue.AddFirst(pageNum);
        }
    }

    public void PrintQueue()
    {
        while (queue.Count > 0)
        {
            Console.WriteLine(queue.First() + " ");
            queue.RemoveFirst();
        }
    }
}